import java.util.Arrays;

/*
 * @lc app=leetcode.cn id=1049 lang=java
 *
 * [1049] 最后一块石头的重量 II
 */

// @lc code=start
class Solution {
    //关键点在于想到实际就是划分为两个重量相近的集合
    public int lastStoneWeightII(int[] stones) {
        if(stones.length==1) return stones[0];
        int sum=Arrays.stream(stones).sum();
        int target=sum/2;
        int[] dp=new int[sum];
        for(int i=0;i<stones.length;i++){
            for(int j=target;j>=stones[i];j--){
                dp[j]=Math.max(dp[j], dp[j-stones[i]]+stones[i]);
            }
        }
        return (sum-dp[target])-dp[target];//分成两个集合

    }
}
// @lc code=end

